// 2025/10/24
// 除法求值

class Solution {
public:
    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
        int nvars = 0;
        unordered_map<string, int> variables;
        for(auto &equation : equations)
        {
            if(variables.count(equation[0]) == 0)
                variables[equation[0]] = nvars++;
            if(variables.count(equation[1]) == 0)
                variables[equation[1]] = nvars++;
        }

        vector<vector<pair<int, double>>> edges(nvars);
        int n = equations.size();
        for(int i = 0; i < n; i++)
        {
            int va = variables[equations[i][0]], vb = variables[equations[i][1]];
            edges[va].emplace_back(vb, values[i]);
            edges[vb].emplace_back(va, 1.0 / values[i]);
        }

        vector<vector<double>> result(nvars, vector<double>(nvars, -1.0));
        for(int i = 0; i < nvars; i++) result[i][i] = 1.0;
        vector<double> ans;
        for(auto &query : queries)
        {
            if(variables.count(query[0]) && variables.count(query[1]))
            {
                int va = variables[query[0]], vb = variables[query[1]];
                if(result[va][vb] == -1.0)
                {
                    queue<int> q;
                    q.emplace(va);
                    while(!q.empty())
                    {
                        int cur = q.front();
                        q.pop();

                        for(auto &pr : edges[cur])
                        {
                            if(result[va][pr.first] < 0)
                            {
                                result[va][pr.first] = result[va][cur] * pr.second;;
                                q.emplace(pr.first);
                            }
                        }
                    }
                }
                ans.emplace_back(result[va][vb]);
            }
            else
                ans.emplace_back(-1.0);
        }
        return ans;
    }
};